package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-21
 * Time:17:46
 */

/**
 * 力扣面试经典150:86. 分隔链表
 * 已解答
 * 中等
 * 相关标签
 * 相关企业
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 * 示例 1：
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 */
public class partition {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode post = dummy;

        while(post != null && post.next != null) {
            if(post.next.val < x) {
                if(post != pre) {
                    ListNode next = post.next.next;
                    post.next.next = pre.next;
                    pre.next = post.next;
                    post.next = next;
                } else {
                    post = post.next;
                }
                pre = pre.next;
            } else {
                post = post.next;
            }
        }

        return dummy.next;
    }
}
